The capabilities of collecting people's location data have been growing rapidly with the fast progress of mobile, satellite, sensor, and video technologies. These spatial moving object datasets have enabled numerous new applications. Social networking services such as Facebook and Foursquare discover other people nearby a user; retail stores and malls combine real-time customer location data with geo-fencing for targeted marketing; mobility managers embed GPS in cars/taxis to better monitor and guide vehicles; animal scientists attach telemetry equipment on the wildlife to analyze ecological behavior. Massive-scale moving object data are becoming ubiquitous.
The Holy Grail is to design a scalable method that can efficiently handle frequent updates and search this massive ever-changing spatial data. However, the challenge is that there is a tradeoff between search and update in index structures; namely, an index is either update or search efficient.
Although moving object index structures alleviate this tradeoff to some extent with sophisticated techniques, massive data, frequent updates and large query volume give rise to a major scalability problem given the performance bottleneck of their single-server designs. In addition, these moving object indexing approaches make the simplifying assumption that extra information about the objects' movement behavior exists (e.g., direction and velocity). Due to the above reasons and also because of the complexity of maintaining these index structures, unfortunately they have not been deployed in any real-world system or application.
Alternatively, another group of studies focused on devising distributed versions of successful spatial index structures, leveraging the power of cluster of servers to scale out. However, their focus has not been on moving objects that result in frequent index updates, which is even less efficient with a distributed index structure than its centralized version due to the high network cost.
Accordingly, it is desirable to provide a system whereby server nodes may be leveraged for efficient data updates.